Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings.

Originality As far as I can tell, the authors' claim that this is the first such work is correct. Previous work has been done is describing heuristics or empirical understandings of such behaviour, but the work is nonetheless original in proving a theoretical basis for this. Quality The authors' exposition of the problem and the solution is well thought out and expertly laid out in a logical and convincing form. However, the excellent technical contribution is somewhat lacking in discussion, particularly given the authors aim to bridge the gap between theory and practice; such claims as "This new consequence may serve an important guide for practical considerations" warrant a standalone discussion section which is not provided. Further, the results predicted in theory could have been compared to empirical experiments to show tightness in practice, and phase transitions could be shown in experiments as a demonstration.

This is a very interesting paper, which presents a comprehensive theoretical analysis of metric dimensionality reduction. It describe existing distortion measures in terms of moments of distortions and give an average case performance guarantee for these moments of distortion. Also, an approximate algorithm with provable guarantees on metric dimensionality reduction is introduced. The main objection on this paper was the absence of empirical evidence to support the claims. The authors have conducted additional experiments in the rebuttal phase but there are missing details regarding the experiments. The authors are advised to improve the quality of their paper in light of the reviewers' comments and incorporate their recommended changes.

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings.

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings.